package heap_trianning

import (
	"traning/algorithm/utility"
	"traning/algorithm/utility/heap02"
)

// 1. 暴力解法
func GetMaxRepeatLineNum(lines [][]int) int {
	min, max := 0, 0
	for _, line := range lines {
		min = utility.Min(line[0], min)
		max = utility.Max(line[0], max)
	}
	var ans int
	for i:=min; i<max; i++ {
		sag := float64(i) + 0.5
		curRepeat := 0
		for _, line := range lines {
			if float64(line[0]) < sag && sag < float64(line[1]) {
				curRepeat++
			}
		}
		ans = utility.Max(ans, curRepeat)
	}
	return ans
}



// 2. 使用堆
func GetMaxRepeatLineNum2(lines [][]int) int {
	myLines := SortableLines(lines)
	hp := heap02.NewHeap(len(lines), func (a interface{}, b interface{}) bool { // 小根堆，自定义比较器
		return a.(int) < b.(int)
	})
	var ans int
	for _, line := range myLines {
		for hp.Peek() != nil &&  hp.Peek().(int) < line[0] {
			hp.Poll()
		}
		hp.Add(line[1])
		ans = utility.Max(ans, hp.Size())
	}
	return ans
}

type SortableLines [][]int

func (s SortableLines) Len() int {
	return len(s)
}

func (s SortableLines) Less(i, j int) bool {
	return s[i][0] < s[j][0]
}

func (s SortableLines) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}